문제 14369

전화번호 수수께끼(Small)

입력 : 첫 줄에 테스트케이스의 개수 T가 주어진다. 각 테스트케이스에는 상대방이 제시한 스트링 S가 주어진다. S는 영어 대문자로만 이루어져 있다.
1≤ T ≤ 100이고, S의 길이는 3 이상 20 이하이다. 모든 테스트케이스에는 유일한 해답이 있다.
출력 : 각 줄에 테스트케이스 번호 x와 전화번호 y를 Case # x: y의 형태로 출력한다.

첫 시도 -> 시간초과

ZERO = [1,0,0,0,0,0,1,1,0,0,0,0,0,0,1]
ONE =  [1,0,0,0,0,1,1,0,0,0,0,0,0,0,0]
TWO =  [0,0,0,0,0,0,1,0,0,1,0,0,1,0,0]
THREE =[2,0,0,1,0,0,0,1,0,1,0,0,0,0,0]
FOUR = [0,1,0,0,0,0,1,1,0,0,1,0,0,0,0]
FIVE = [1,1,0,0,1,0,0,0,0,0,0,1,0,0,0]
SIX =  [0,0,0,0,1,0,0,0,1,0,0,0,0,1,0]
SEVEN =[2,0,0,0,0,1,0,0,1,0,0,1,0,0,0]
EIGHT =[1,0,1,1,1,0,0,0,0,1,0,0,0,0,0]
NINE = [1,0,0,0,1,2,0,0,0,0,0,0,0,0,0]
NUMBER = [ ["0",ZERO], ["1", ONE], ["2", TWO], ["3", THREE], ["4", FOUR], ["5", FIVE], ["6", SIX], ["7", SEVEN], ["8", EIGHT], ["9",NINE] ]
ALPHABET = ['E', 'F', 'G', 'H', 'I', 'N', 'O', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Z']


def CASE(TEXT, ALPHABET = ALPHABET):
    result = []
    for i in ALPHABET:
        result.append(TEXT.count(i))
    return result


def CLEAR_NUMBER(NUMBER = NUMBER, case = []):
    number = []
    #전처리
    for i in NUMBER:
        detect = 0
        for j in range(15):
            if i[1][j] > case[j]:
                detect = 1
                break
        if detect == 0:
            number.append(i)
            case = [y-x for x,y in zip(i[1], case)]

    return number, case


def ANSWER(case, number = NUMBER):
    answer = []
    case = CASE(case)
    while True:
        if case == [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]:
            break
        number, case = CLEAR_NUMBER(number, case)
        for i in number:
            answer.append(i[0])

    return answer

answer = []
for i in range(int(input())):
    case = input()
    a = ""
    for j in sorted(ANSWER(case)):
        a += j
    answer.append(a)

m = 1
for i in answer:
    print("Case "+"#"+str(m)+": "+i)
    m += 1

'E', 'F', 'G', 'H', 'I', 'N', 'O', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Z' 를 차례대로 묶어서, 해당 알파벳이 있으면 1, 없으면 0을 매겨주었다. 그리고 주어진 case에서, 해당되는 알파벳 부분을 전체에서 빼주는 작업을
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 이 될 때까지 반복해서
정답을 찾는 방법으로 작성했다.

CLEAR_NUMBER 함수는 NUMBER 리스트를 순회하면서 각 숫자의 패턴과 case를 비교하는데, 매 숫자마다 15개의 값을 비교하고, 이를 매번 갱신하며 반복적으로 수행하는 점이 시간을 많이 잡아먹었고.. case가 0으로 수렴하는 과정에서 반복 횟수가 많아지고, 내부적으로 CLEAR_NUMBER를 여러 번 호출하므로 시간이 크게 소요되어서 시간초과가 났을 것이다.

네 번째 시도

from collections import Counter

DIGITS = [
    ["0", "Z", "ZERO"],
    ["2", "W", "TWO"],
    ["4", "U", "FOUR"],
    ["6", "X", "SIX"],
    ["8", "G", "EIGHT"],
    ["3", "H", "THREE"],
    ["5", "F", "FIVE"],
    ["7", "V", "SEVEN"],
    ["1", "O", "ONE"],
    ["9", "I", "NINE"],
]

def solve_case(case):
    case_count = Counter(case)
    result = []

    for digit, unique_char, word in DIGITS:
        count = case_count[unique_char]
        if count > 0:
            result.extend([digit] * count)
            for char in word:
                case_count[char] -= count

    return "".join(sorted(result))

# 입력 처리
t = int(input())
answers = []
for i in range(t):
    case = input().strip()
    answers.append(f"Case #{i + 1}: {solve_case(case)}")

print("\n".join(answers))

그냥 아예 각 알파벳이 고유하게 가지고 있는 문자열을 비교해서 빼주는 방식으로 진행했다.

["1", "O", "ONE"] 같은 경우 "O"가 "ZERO"에도 있고 "TWO"에도 있고 "FOUR" 에도 있기 때문에 문제가 될 거 같지만 애당초 "ZERO"는 유일한 "Z"에 의해 다 걸러지게 되고, 마찬가지로 "TWO"는 "W"에, "FOUR"는 "U"에 걸러지게 되므로 상관 없다.
from collections import Counter를 사용해서 시간을 줄였다.